package com.sx.sx1.lintcode.day717;

import java.util.TreeMap;

public class LC3745 {

    static class Solution {
        /**
         * @param lights: Location and extent of illumination of street lights
         * @return: The brightest position
         */
        public int brightestPosition(int[][] lights) {
            /*
        解题思路
        方法：差分数组 + 哈希表
        我们可以将每一个路灯照亮的范围看作是一个区间，区间左端点
        l=position−range，区间右端点
        r=position+range。我们利用差分数组的思想，对于每个区间
        [l, r]，将位置l 的值增加 1，将位置r+1 的值减少 1，用哈希表维护每个位置的变化值。

        然后从小到大遍历每个位置，计算当前位置的亮度 s，如果此前的最大亮度
        mx<s，则更新最大亮度
        mx=s，并记录当前位置
        res=i。
         */
            TreeMap<Integer,Integer> ts = new TreeMap<>();
            for (int[] v : lights) {
                int L = v[0]-v[1];
                int R = v[0]+v[1]+1;
                if(!ts.containsKey(L))
                    ts.put(L,0);
                ts.put(L,ts.get(L)+1);

                if(!ts.containsKey(R))
                    ts.put(R,0);
                ts.put(R,ts.get(R)-1);
            }

            int ans =Integer.MIN_VALUE;
            int sum=0;
            int max = Integer.MIN_VALUE;

            for(int k: ts.keySet()){
                int v = ts.get(k);
                sum+=v;
                if(max <sum){
                    max =sum;
                    ans =k;
                }
            }

            return ans;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.brightestPosition(new int[][]{{-3, 2}, {1, 2}, {3, 2}}));
    }
}

/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有189条未读消息，请及时查看
3745 · 街上最亮的位置
算法
中等
通过率
29%

题目
题解4
笔记
讨论1
排名
记录
描述
一条街上有很多的路灯，路灯的坐标由数组 lights 的形式给出，每个 lights[i] = [position, range] 表示坐标位于 position 的路灯，可以照亮包括边界点在内的范围 [position - range, position + range]。

当某个位置 p，存在被多个路灯照亮时，这个位置会更亮一点，现在给定 lights ，返回 最亮的横坐标位置，如果 存在多个亮度一样的位置，返回坐标最小的。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


1
≤
𝑙
𝑖
𝑔
ℎ
𝑡
𝑠
.
𝑙
𝑒
𝑛
𝑔
𝑡
ℎ
≤
1
0
5
1≤lights.length≤10
5

𝑙
𝑖
𝑔
ℎ
𝑡
𝑠
[
𝑖
]
.
𝑙
𝑒
𝑛
𝑔
𝑡
ℎ
=
=
2
lights[i].length==2
−
1
0
8
≤
𝑝
𝑜
𝑠
𝑖
𝑡
𝑖
𝑜
𝑛
≤
1
0
8
−10
8
 ≤position≤10
8

0
≤
𝑟
𝑎
𝑛
𝑔
𝑒
≤
1
0
8
0≤range≤10
8


样例
样例 1：

输入：
lights = [[-3, 2], [1, 2], [3, 2]]
输出：
-1
解释：
第一个路灯照亮的范围是 [-5, -1]
第二个路灯照亮的范围是 [-1, 3]
第三个路灯照亮的范围是 [1, 5]
位置 -1，1，2，3 都被两个路灯照亮
因此返回坐标最小的 -1
3745.png

样例 2：

输入：
lights = [[1, 0], [0, 1]]
输出：
1
标签
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
已开启智能提示
发起考试
30 分 00 秒
123456789
public class Solution {

public int brightestPosition(int[][] lights) {
    // write your code here
}
}
控制台
        历史提交

 */